package offer;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

public interface SimplifiedFractions {
    /**
     * Given an integer n, return a list of all simplified fractions between 0 and 1 (exclusive) such that the denominator is less-than-or-equal-to n.
     * You can return the answer in any order.
     *
\
     * @param n
     * @return
     */
    List<String> simplifiedFractions(int n);
}
class SimplifiedFractionsImpl1 implements SimplifiedFractions{
    public static void main(String[] args) {
        for (int i = 2; i < 10; i++) {
            System.out.println(i);
            System.out.println("=========================================");
            List<String> ans = new SimplifiedFractionsImpl1().simplifiedFractions(i);
            for(String item : ans){
                System.out.print(item+",");
            }
            System.out.println("");
        }


    }

    @Override
    public List<String> simplifiedFractions(int n) {
        List<String> ans = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                int gcd = gcd(j,i);
                if(gcd == 1){
                    String item = j + "/" + i;
                    ans.add(item);
                }
            }
        }
        return ans;
    }

    private int gcd(int numerator, int denominator){
        int temp;
        while (numerator != 0){
            temp = denominator % numerator;
            denominator = numerator;
            numerator = temp;
        }
        return denominator;
    }


}
